package com.bing.java.stack;

import java.util.Iterator;

/**
 * 自定义栈
 * 链表实现
 * @author bing
 *
 * 2019年11月9日 下午3:12:57
 * 
 * 需要使用链表的头插法来实现，因为头插法中最后压入栈的元素在链表的开头，它的 next 指针指向前一个压入栈的元素，在弹出元素时
 * 就可以通过 next 指针遍历到前一个压入栈的元素从而让这个元素成为新的栈顶元素。
 */
public class ListStack<Item> implements MyStack<Item> {

	private Node top = null;   //当前节点
	private int N = 0;

	private class Node {
		Item item;     //当前节点
		Node next;     //上一个节点
	}

	@Override
	public MyStack<Item> push(Item item) {

		Node newTop = new Node();

		newTop.item = item;    //当前元素为第一个元素
		newTop.next = top;     //上一个元素为Null

		top = newTop;          //当前元素就是进来得这个值

		N++;                   // 长度加1

		return this;
	}

	@Override
	public Item pop() throws Exception {

		if (isEmpty()) {
			throw new Exception("stack is empty");
		}

		Item item = top.item;     //当前节点元素去除

		top = top.next;      //将当前节点设置为上一个节点。
		N--;

		return item;
	}

	@Override
	public boolean isEmpty() {
		return N == 0;
	}

	@Override
	public int size() {
		return N;
	}

	@Override
	public Iterator<Item> iterator() {

		return new Iterator<Item>() {

			private Node cur = top;

			@Override
			public boolean hasNext() {
				return cur != null;
			}

			@Override
			public Item next() {
				Item item = cur.item;
				cur = cur.next;
				return item;
			}
		};

	}
	
	public static void main(String[] args) throws Exception {
		ListStack<Integer> listStack = new ListStack<Integer>();
		listStack.push(8);
		listStack.push(9);
		listStack.pop();
	}
}
